import networkx as nx
import collections
import functools

class memoize:
  # From https://github.com/S2E/s2e-env/blob/master/s2e_env/utils/memoize.py

  def __init__(self, func):
    self._func = func
    self._cache = {}

  def __call__(self, *args):
    if not isinstance(args, collections.abc.Hashable):
      return self._func(args)

    if args in self._cache:
      return self._cache[args]

    value = self._func(*args)
    self._cache[args] = value
    return value

  def __repr__(self):
    # Return the function's docstring
    return self._func.__doc__

  def __get__(self, obj, objtype):
    # Support instance methods
    return functools.partial(self.__call__, obj)

dotfilename = './callgraph.dot'

G = nx.DiGraph(nx.drawing.nx_pydot.read_dot(dotfilename))
print(nx.info(G))

def node_name(name):
  return "\"{%s}\""%name

@memoize
def find_nodes(name):
  n_name = node_name(name)
  return [(n,d) for n,d in G.nodes(data=True) if n_name in d.get('label', '')]

vulNodes = find_nodes('xmlBufAdd')
callstack = []
visited = set()

def get_predecessors(node):
  if G.in_degree(node) == 0:
    for n in callstack:
      print(G.nodes[n]['label'])
    print('-'*30)
    return

  for n in G.predecessors(node):
    if n in visited:      
      for func in callstack:
        print(G.nodes[func]['label'])
      print(G.nodes[n]['label'])
      print('repeat')
      print('-'*30)      
      continue
    callstack.append(n)
    visited.add(n)
    get_predecessors(n)
    callstack.pop()
    
for node,data in vulNodes:
  callstack.append(node)
  get_predecessors(node)
  callstack.pop()